// 先序遍历
var preorderTraversal = function(root) {
    let res = []
    const dfs = function(root){
        if(!root){
            return
        }
        res.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
};

//切换 res.push()的位置就可以实现  中序遍历  后续遍历


//迭代版本
/**
 * 先序遍历 栈的思想
 * @param {*} root 
 * @returns 
 */
var preorderTraversal = function(root){
    let res = []
    if(!root) return res
    let stack = [root]
    while(!stack.length){
        let node = stack.pop()
        res.push(node.val)
        node.right && res.push(node.right) 
        node.left && res.push(node.left)
    }
}
/**
 * 后续遍历
 * @param {*} root 
 * @returns 
 */

var subsequentTraversal = function(root){
    let res = []
    if(!root) return res
    let stack = [root]
    while(stack.length){
        let node = stack.pop()
        res.push(node.val)
        node.left && stack.push(node.left)
        node.right && stack.push(node.right)
    }
    return res.reverse()
}

/**
 * 中序遍历
 * @param {*} root 
 * @returns 
 */

var inorderTraversal = function (root){
    let start = [],
        res = [],
        cur = root;
    while(start.length||cur){
        if(cur){
            start.push(cur)
            cur = cur.left
        }else{
            cur = start.pop()
            res.push(cur.val)
            cur = cur.right
        }
    };
    return res;

}